#include "tools.cpp"
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
  public:
    static constexpr int sub_size = 2;
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* result = nullptr;
        lowestCommonAncestor(root, p, q, result);
        std::cout << result->val << std::endl;
        return result;
    }

    int lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q,
                             TreeNode*& result) {
        if (root == nullptr) return 0;
        int left = lowestCommonAncestor(root->left, p, q, result);
        if (left == sub_size) return sub_size;
        int right = lowestCommonAncestor(root->right, p, q, result);
        if (right == sub_size) return sub_size;
        if (right + left == sub_size) {
            result = root;
            return sub_size;
        }

        int sum = left + right;
        if (root == p or root == q) ++sum;
        if (sum == sub_size) result = root;
        return sum;
    }
};

int main() {
    TreeNode root{std::vector<int>{3, 5, 1, 6, 2, 0, 8, INT_MIN, INT_MIN, 7, 4}};
    auto p = root.left;
    auto q = root.left->right->right;
    Solution s;
    s.lowestCommonAncestor(&root, q, p);
}
